package test_new;

import java.io.FileNotFoundException;

public class MergeSortTmp {


    public static int[] mergeSort(int[] arr) {  
        if (arr.length <= 1)  return arr;  
      
        int mid = arr.length / 2;  
        int[] left = new int[mid];  
        int[] right = new int[mid + arr.length%2];  
      
        int j = 0;  
        for (int i = 0; i < arr.length; i++) {  
            if (i < arr.length / 2) {  
                left[i] = arr[i];  
            } else {  
                right[j++] = arr[i];  
            }  
        }  
        return Merge(mergeSort(left), mergeSort(right));  
    }  
      
    public static int[] Merge(int[] left, int[] right) {  
        int a = 0, b = 0;  
        int[] merged = new int[left.length + right.length];  
        for (int i = 0; i < left.length + right.length; i++) {  
            if (b < right.length && a < left.length)  
                if (left[a] > right[b] && b < right.length)  
                    merged[i] = right[b++];  
                else  
                    merged[i] = left[a++];  
            else  
                if (b < right.length)  
                    merged[i] = right[b++];  
                else  
                    merged[i] = left[a++];  
        }  
        return merged;  
    }  

    public static void main(String... args) throws FileNotFoundException {

        int[] p = {4, 6, 7, 1, 9, 2, 5, 3, 8};

        int[] result = mergeSort(p);

        for (int i = 0; i < result.length; i++) {
           System.out.println(result[i]);

        }

    }
}
